package _剑指offer._回溯;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 
 * @author Liu Huan
 */

public class _17_电话号码的字母组合 {
	public static void main(String[] args) {
		String digits = "23";
		List<String> ans = letterCombinations(digits);
		for (String str : ans) {
			System.out.print(str + "\t");
		}
	}
	
	// 存储结果的list ans
	private static List<String> ans = new ArrayList<>();
	// 存储数字->字符的映射map phone
	private static Map<Character, String> phone = new HashMap(){{
		put('2', "abc");
		put('3', "def");
		put('4', "ghi");
		put('5', "jkl");
		put('6', "mno");
		put('7', "pqrs");
		put('8', "tuv");
		put('9', "wxyz");
	}};
	// 存储当前字符串
	private static StringBuilder str = new StringBuilder();
	
	
	public static List<String> letterCombinations(String digits) {
		if(digits.length()==0)   return ans;
		back(digits, 0);
		return ans;
	}
	
	/**
	 * 回溯法拼接字符串
	 * @param digits 数字字符
	 * @param index 对应数字字符的下标位置， 0 开始
	 */
	public static void back(String digits, int index){
		if(index == digits.length()){   //如果拼接到最后一个字符，记录答案
			ans.add(str.toString());
			return;
		} else {                        // 拼接下标为 index 的字符
			// 获取 index 对应的 字符 和 映射 字符串
			// 遍历 字符串 中的每个字符，拼接到 str, 回溯拼接第index+1个字符直至结束，删除当前拼接的字符并continue 
			char ch = digits.charAt(index);
			String digStr = phone.get(ch);
			for (int i = 0; i < digStr.length(); i++) {
				str.append(digStr.charAt(i));
				back(digits, index+1);
				str.deleteCharAt(index);
			}
		}
	}
}
